package leetcode_题库;

import java.util.*;

public class _3_无重复字符的最长子串 {
    public static void main(String[] args) {
//        String s = "abcabcbb";
//        String s = "bbbb";
//        String s = "abba";
//        String s = "dvdf";
        String s = "pwwkew";
        System.err.println(lengthOfLongestSubstring(s));
    }

    /**
     * > 2023/03/22 13:17:00
     * 解答成功:
     * 执行耗时:4 ms,击败了86.64% 的Java用户
     * 内存消耗:41.3 MB,击败了87.15% 的Java用户
     *
     * @param s 原字符串
     * @return 最大子串长度
     */
    public static int lengthOfLongestSubstring(String s) {
        //定义哈希表，键是s的每一个字符，值是字符最后出现的位置
        HashMap<Character, Integer> map = new HashMap<>(s.length());
        //定义左右指针（窗口）
        int lp = 0;
        int rp = 0;
        //定义max，记录遇到重复元素时的最大长度
        int max = 0;
        //将字符串转为字符数组
        char[] chars = s.toCharArray();
        //遍历右窗口
        while (rp < chars.length) {
            //是否找到了重复key
            if (map.containsKey(chars[rp])) {
                max = Math.max(max, rp - lp);
                //由于找到了重复字符，我们可能需要让左指针（窗口）更新位置
                //若该位置在左指针+1的右侧（不能让左窗口左滑），那么我们让左窗口停留在第一个重复的字符的右一个位置
                /*
                    为什么要加Math.max，比如abba这个字符串，第二个b处lp变成2，下一步时，a由重合.
                    如果不比较，则lp变成1，而rp为4，最后return时，就会返回3，这明显错误。
                    因此该操作是为了防止左窗口左滑.
                 */
                lp = Math.max(map.get(chars[rp]) + 1, lp);
            }
            //无论是否重复，put都是通用的，同样的键，不一样的值会被替换
            map.put(chars[rp], rp);
            //右指针（窗口）右移
            rp++;
        }
        //最后，若整体是无重复的，maxLength将会是0，此时rp-lp就是最大的
        return Math.max(max, rp - lp);
    }

    /**
     * > 2023/03/22 12:49:21
     * 解答成功:
     * 执行耗时:54 ms,击败了13.67% 的Java用户
     * 内存消耗:42.2 MB,击败了8.41% 的Java用户
     *
     * @param s 原字符串
     * @return 最大子串长度
     * @Description 这个方法更简单理解，因为set不会存储角标，但是内存和耗时并不理想。
     * 这是因为只要遇到重复字符，就会将窗口回归到原lp+1，可能会多次重复遍历和set操作
     */
    public static int lengthOfLongestSubstring2(String s) {
        //定义左右指针（窗口）
        int lp = 0;
        int rp = 0;
        //定义max，记录遇到重复元素时的最大长度
        int max = 0;
        //定义Set集合，set具有天然去重，所以只要add为false，则说明遇到重复的元素，不需要记录角标
        Set<Character> set = new HashSet<>(s.length());
        //转成字符数粗，其实直接用s.CharAt在这种短字符串上会更快
        char[] chars = s.toCharArray();
        //当右窗口还在字符串内，一直循环
        while (rp < chars.length) {
            if (set.add(chars[rp])) {
                //能add，右窗口++
                rp++;
            } else {
                //不能add，记录比较最大值
                max = Math.max(max, rp - lp);
                //左窗口+1，右窗口也+1
                rp = ++lp;
                //清空set
                set.clear();
            }
        }
        //这里存在有必要意义，举个极端的例子，如果没有重复元素的abcde，由于没有触发add失败，不走else，max一定是0
        //此时就需要取窗口长度rp-lp=5
        return Math.max(max, rp - lp);
    }
}
